home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / raytrace / radiance / simplerd.lha / simplerad / FinalFTP / Light / inter.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-20  |  18.1 KB  |  526 lines
  1. /**********************************************************************/
  2. /* inter.c                                                            */
  3. /*                                                                    */
  4. /* Ray / Object intersection routines.                                */
  5. /* Some routines modified from Optik v(1.2e) (C) 1987 by John         */
  6. /* Amanatides and Andrew Woo.                                         */
  7. /*                                                                    */
  8. /* Copyright (C) 1992, Bernard Kwok                                   */
  9. /* All rights reserved.                                               */
  10. /* Revision 1.0                                                       */
  11. /* May, 1992                                                          */
  12. /**********************************************************************/
  13. #include <stdio.h>
  14. #include "geo.h"
  15. #include "struct.h"
  16. #include "misc.h"
  17. #include "io.h"
  18. #include "ray.h"
  19. #include "bvol.h"
  20. #include "ff.h"
  21. #include "rtime.h"
  22.  
  23. /**********************************************************************/
  24. extern OptionType Option;   /* Options */
  25. extern FF_OptionType FF_Options;
  26. extern Object_List *objlist;
  27. extern int objlist_size;
  28. extern Polygon *shootPatch;
  29. extern Polygon *recPatch;
  30. extern Scene RadScene;      /* The scene */
  31. extern HBBox Scene_BVH;     /* Hierarchical bounding boxes for scene */
  32. extern Time_Stats tstats;
  33. extern FILE *rlogfile;
  34.  
  35. extern void HitTransform(); 
  36. extern void RayTransform();
  37. extern Plane PlaneTransform();
  38. extern 
  39.   BoundingBoxType BoundingBoxTransform(), BoxCube(), BoxCone(), BoxPoly(),
  40.   BoxSquare(), BoxSphere(), BoxTriangle(), BoxCylinder(),
  41.   BoxDisk();
  42.  
  43. /**********************************************************************/
  44. void StartIntersect();
  45. void EndIntersect();
  46. int HitObject();
  47. void RayObject();
  48. HitData RayIntersect();
  49. void RayPolyBVH();
  50. void RayBVH();
  51.  
  52. RayStats_Type RayStats;           /* Ray statistics */
  53.  
  54. /**********************************************************************/
  55. /* Start ray intersection: Clear statistics                           */
  56. /**********************************************************************/
  57. void StartIntersect()
  58. {
  59.   RayStats.currentRayID = 1;
  60.   RayStats.numRays = RayStats.intRay = RayStats.intRayID = 0;
  61.   RayStats.intCone = RayStats.intCube = RayStats.intSphere = 0;
  62.   RayStats.intPoly = 0;
  63.   RayStats.rayCone = RayStats.rayCube = RayStats.raySphere = 0;
  64.   RayStats.rayMesh = RayStats.rayPoly = 0;
  65.   RayStats.rayBox = RayStats.intBox = 0;
  66. }
  67.  
  68. /**********************************************************************/
  69. /* Print stats after intersection pass */
  70. /**********************************************************************/
  71. void EndIntersect(fptr)
  72.      FILE *fptr;
  73. {
  74.   FILE *fp;
  75.  
  76.   if (Option.statistics && RayStats.numRays != 0) {
  77.     if (Option.device == PRINT)       
  78.       fp = stdout;
  79.     else fp = fptr;
  80.     
  81.     fprintf(fp,"\n\tRay Tracing Statistics\n");
  82.     fprintf(fp,"\t----------------------\n");
  83.     fprintf(fp,"\tTotal number of rays shot = %ld\n", RayStats.numRays);
  84.     fprintf(fp,"\tAverage number of intersections per ray = %g\n", 
  85.           (double)RayStats.intRay/(double)RayStats.numRays);
  86.     if (Option.grid)
  87.       fprintf(fp,"\tAverage number of intersections per ray (BV) = %g\n",
  88.           (float) RayStats.intBox / (float)RayStats.numRays);
  89.     
  90.     fprintf(fp,"\tAverage number of intersections per ray with:\n");
  91.     fprintf(fp,"\tCube=%g; Cone=%g; Cyl=%g; Sph=%g; Mesh=%g; Poly=%g\n",
  92.         (float) RayStats.intCube / (float)RayStats.numRays,
  93.         (float) RayStats.intCone / (float)RayStats.numRays,
  94.         (float) RayStats.intCylinder / (float)RayStats.numRays,
  95.         (float) RayStats.intSphere / (float)RayStats.numRays,
  96.         (float) RayStats.rayMesh /  (float)RayStats.numRays,
  97.         (float) RayStats.intPoly / (float)RayStats.numRays);
  98.     
  99.     fprintf(fp,"\tAverage number of ray tests per ray with:\n");
  100.     fprintf(fp,
  101.         "\tBV=%g; Cube=%g; Cone=%g; Cyl=%g; Sph=%g; Mesh=%g; Poly=%g\n",
  102.         (float) RayStats.rayBox / (float)RayStats.numRays,
  103.         (float) RayStats.rayCube / (float)RayStats.numRays,
  104.         (float) RayStats.rayCone / (float)RayStats.numRays,
  105.         (float) RayStats.rayCylinder / (float)RayStats.numRays,
  106.         (float) RayStats.raySphere / (float)RayStats.numRays,
  107.         (float) RayStats.rayMesh /  (float)RayStats.numRays,
  108.         (float) RayStats.rayPoly / (float)RayStats.numRays);
  109.     
  110.     fprintf(fp,"\tAverage number of intersections per ray test with:\n");
  111.     fprintf(fp,
  112.         "\tBV=%g; Cube=%g; Cone=%g; Cyl=%g; Sph=%g; Mesh=%g; Poly=%g\n",
  113.         (float) RayStats.intBox / ((float) RayStats.rayBox > 0.0 ?
  114.                        RayStats.rayBox : 1.0),
  115.         (float) RayStats.intCube / ((float) RayStats.rayCube > 0.0 ?
  116.                     RayStats.rayCube : 1.0),
  117.         (float) RayStats.intCone / ((float) RayStats.rayCone > 0.0 ?
  118.                     RayStats.rayCone : 1.0),
  119.         (float) RayStats.intCylinder / 
  120.         ((float) RayStats.rayCylinder > 0.0 ? RayStats.rayCylinder : 1.0),
  121.         (float) RayStats.intSphere / ((float) RayStats.raySphere > 0.0 ?
  122.                       RayStats.raySphere : 1.0),
  123.         (float) RayStats.rayMesh,
  124.         (float) RayStats.intPoly / ((float) RayStats.rayPoly > 0.0 ?
  125.                     RayStats.rayPoly : 1.0));
  126.     fprintf (fp,"\n");
  127.  
  128.     if (Option.tablelog) {
  129.       fp = rlogfile;
  130.       
  131.       fprintf(fp,"%ld \\\\\n", RayStats.numRays);
  132.       fprintf(fp,"%g \\\\\n", 
  133.           (double)RayStats.intRay/(double)RayStats.numRays);
  134.       if (Option.grid)
  135.     fprintf(fp,"%g \\\\\n",
  136.         (float) RayStats.intBox / (float)RayStats.numRays);
  137.       fprintf(fp,"%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n",
  138.           (float) RayStats.intCube / (float)RayStats.numRays,
  139.           (float) RayStats.intCone / (float)RayStats.numRays,
  140.           (float) RayStats.intCylinder / (float)RayStats.numRays,
  141.           (float) RayStats.intSphere / (float)RayStats.numRays,
  142.           (float) RayStats.rayMesh /  (float)RayStats.numRays,
  143.           (float) RayStats.intPoly / (float)RayStats.numRays);
  144.       
  145.       fprintf(fp,"%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n",
  146.           (float) RayStats.rayBox / (float)RayStats.numRays,
  147.           (float) RayStats.rayCube / (float)RayStats.numRays,
  148.           (float) RayStats.rayCone / (float)RayStats.numRays,
  149.           (float) RayStats.rayCylinder / (float)RayStats.numRays,
  150.           (float) RayStats.raySphere / (float)RayStats.numRays,
  151.           (float) RayStats.rayMesh /  (float)RayStats.numRays,
  152.           (float) RayStats.rayPoly / (float)RayStats.numRays);
  153.       
  154.       fprintf(fp,"%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n%g \\\\\n",
  155.           (float) RayStats.intBox / ((float) RayStats.rayBox > 0.0 ?
  156.                      RayStats.rayBox : 1.0),
  157.           (float) RayStats.intCube / ((float) RayStats.rayCube > 0.0 ?
  158.                       RayStats.rayCube : 1.0),
  159.           (float) RayStats.intCone / ((float) RayStats.rayCone > 0.0 ?
  160.                       RayStats.rayCone : 1.0),
  161.           (float) RayStats.intCylinder / 
  162.           ((float) RayStats.rayCylinder >0.0 ? RayStats.rayCylinder : 1.0),
  163.           (float) RayStats.intSphere / ((float) RayStats.raySphere > 0.0 ?
  164.                         RayStats.raySphere : 1.0),
  165.           (float) RayStats.rayMesh,
  166.           (float) RayStats.intPoly / ((float) RayStats.rayPoly > 0.0 ?
  167.                       RayStats.rayPoly : 1.0));
  168.     }
  169.   }
  170.   
  171.   tstats.avg_ray /= (float) RayStats.numRays;
  172. }
  173.  
  174. /**********************************************************************/
  175. /* Returns 0=cannot see object in direction raydir within given       */
  176. /* distance or 1=can see object in ray direction raydir within given  */
  177. /* distance (for form-factor visibility testing)                      */
  178. /**********************************************************************/
  179. int HitObject(point, raydir, distance)
  180.      Vector point, raydir;
  181.      double distance;
  182. {
  183.   HitData hit;
  184.   Ray ray;
  185.  
  186.   if (Option.debug)  printf("\t> Testing visibility\n");
  187.   Option.rayTransform = TRUE;
  188.   Option.visibility = FORM_FACTOR;
  189.   Option.shadow = TRUE;
  190.   ray.origin = point;
  191.   ray.dir = raydir;
  192.   ray.shadow = TRUE;                 /* Doing visibility testing */
  193.   ray.generation = -1;               /* 1st generation */
  194.   ray.visible= 1.0;                  /* Ray can still see destination */
  195.   hit = RayIntersect(ray, distance); /* Find if any intersection */
  196.  
  197.   if (hit.obj == NULL || hit.distance > distance) {
  198.     if (Option.debug) 
  199.       printf("\tObject missed everything!\n\n");
  200.     return(FALSE);         /* Missed everything or too far away */
  201.   } else {
  202.     if (Option.debug) {
  203.       printf("\tHit %s%d [ray vis = %g, dist = %g]\n", 
  204.          hit.obj->name, hit.obj->id, 
  205.          ray.visible, hit.distance);
  206.       if (hit.poly != 0)
  207.     printf("\tPoly %s%d\n", hit.poly->name, hit.poly->id);
  208.     }
  209.     return(TRUE);          /* Hit something along the way close enough */
  210.   }
  211. }
  212.  
  213. /**********************************************************************/
  214. /* Check if ray hits any object */
  215. /**********************************************************************/
  216. void RayObject(ray, hit, optr)
  217.      Ray *ray;
  218.      HitData *hit;
  219.      register Objectt *optr;
  220. {
  221.   switch(optr->primid) {
  222.   case CONE:
  223.     RayCone(ray, hit, optr);           /* Test against cone */
  224.     break;
  225.   case CUBE:
  226.     RayCube(ray, hit, optr);           /* Test against cube */
  227.     break;
  228.   case CYLINDER:
  229.     RayCylinder(ray, hit, optr);       /* Test against cylinder */
  230.     break;
  231.   case MESH:
  232.     RayMesh(ray, hit, optr);           /* Test against polygonal mesh */
  233.     break;
  234.   case SPHERE:
  235.     RaySphere(ray, hit, optr);         /* Test against sphere */
  236.     break;
  237.   default:
  238.     fprintf(stderr,"Invalid primitive type to intersect: %d\n", optr->primid);
  239.     exit(1);
  240.     break;
  241.   }
  242. }
  243.  
  244. /**********************************************************************/
  245. /* Find out what a ray intersects, return hit data (if any).          */
  246. /* The ray is only allowed to travel up to max_distance distance from */
  247. /* the ray origin, if doing form-factor calculatiions.                */
  248. /**********************************************************************/
  249. HitData RayIntersect(ray, max_distance)
  250.      Ray ray;
  251.      double max_distance;
  252. {
  253.   int i;
  254.   Object_List *olptr;
  255.   Objectt *optr;
  256.   HitData hit;
  257.   Ray newRay;
  258.   HBBox *hbox;
  259.   double box_hit_dist;
  260.   float ray_start, ray_end; /* Ray start and end times */
  261.  
  262.   ray.rayID = RayStats.currentRayID++;
  263.   RayStats.numRays++;
  264.   Reset_Hit(&hit,max_distance);        /* Reset hit info */
  265.  
  266.   if (Option.debug) {
  267.     printf("\tShooting Ray [id=%ld]: (%g,%g,%g) -> (%g,%g,%g), mdist=%g\n", 
  268.        ray.rayID, 
  269.        ray.origin.x, ray.origin.y, ray.origin.z, ray.dir.x, 
  270.        ray.dir.y, ray.dir.z, max_distance);
  271.     fflush(stdout);
  272.   }
  273.  
  274.   /* Start time */
  275.   ray_start = Cpu_Time(&tstats.utime, &tstats.stime);  
  276.  
  277.   if (Option.grid) {                   /* Use hierarchical BV tree */
  278.     
  279.     /* Test volumes in candidate list for current shaft */
  280.     if (FF_Options.shaft_cull) {
  281.       i=0; olptr=objlist;
  282.       while (i<objlist_size && ray.visible>0.0) {
  283.     hbox = olptr->hbox;
  284.     if (hbox->poly == NULL) 
  285.       RayBVH(&ray, max_distance, hbox, &hit);
  286.     else if ((hbox->poly != shootPatch) && (hbox->poly != recPatch))
  287.       RayPolyBVH(&ray, max_distance, hbox, &hit);
  288.     i++; 
  289.     olptr = olptr->next;
  290.       }
  291.     }
  292.  
  293.     /* Test volumes of objects in front of current receiver */
  294.     else if (FF_Options.src_rec_cull) {
  295.       i=0; olptr=objlist;
  296.       while (i<objlist_size && ray.visible >0.0) {
  297.     hbox = olptr->hbox;
  298.     /* Only check if object is in front of source and receiver patches */
  299.     if (olptr->is_obstructor) {
  300.       
  301.       /* Test if hit the box around object first. If so,
  302.          then check the BV tree underneath */
  303.       /* newRay = ray;
  304.          RayStats.rayBox++;
  305.          if (RayBoundingBox(*hbox->box, newRay, &box_hit_dist)) 
  306.          if (box_hit_dist < hit.distance) {
  307.          RayStats.intBox++;
  308.          RayStats.intRay++;
  309.          RayStats.intRayID++;
  310.          */
  311.       
  312.       /* Check for intersection */
  313.       RayBVH(&ray, max_distance, hbox, &hit);
  314.     }
  315.     i++; 
  316.     olptr = olptr->next;
  317.       }
  318.     }
  319.     
  320.     /* Traverse through all volumes in whole tree */
  321.     else 
  322.       RayBVH(&ray, max_distance, &Scene_BVH, &hit);
  323.  
  324.   } else {                             /* Don't use hierarchical BV */
  325.     optr = RadScene.objects; i=0;
  326.     
  327.     /* Check all objects in the scene until no more object, or
  328.        hit an object closer than maximum distance */
  329.     while((i<RadScene.num_objects) && (ray.visible>0.0)) {
  330.       newRay = ray;                    /* Test new ray */
  331.       
  332.       /* Transform ray from world to model space first before intersect.
  333.      Note. Do not tranform ray for polygonal meshes. */
  334.       if ((Option.rayTransform) && (optr->primid != MESH))
  335.     RayTransform(&ray, &newRay, *optr->WToM);
  336.       RayObject(&newRay, &hit, optr);
  337.       ray.visible = newRay.visible;
  338.  
  339.       /* Stop if hit object closer than maximum distance ray can travel
  340.      for form factors. Otherwise continue checking. If two objects
  341.      touch at the intersection point assume destination is still 
  342.      visible, and contine checking rest of objects */
  343.       if (Option.visibility == FORM_FACTOR) {
  344.     if (hit.distance < max_distance) {  /* Destination is not visible */
  345.       RayStats.intRay++;
  346.       ray.visible = 0.0;
  347.     }
  348.       }
  349.       optr = optr++; i++;
  350.     }
  351.   }
  352.  
  353.   /* Hit was too close */
  354.   if (hit.obj != NULL && hit.distance < MIN_DISTANCE)
  355.     hit.obj = NULL;
  356.  
  357.   ray_end = Cpu_Time(&tstats.utime, &tstats.stime); 
  358.   tstats.avg_ray += (ray_end - ray_start);
  359.   return(hit);
  360. }
  361.  
  362.  
  363. /**********************************************************************/
  364. /* Ray Polygon-BVH traversal */
  365. /**********************************************************************/
  366. void RayPolyBVH(ray, max_distance, BVtree, hit)
  367.      Ray *ray;
  368.      double max_distance;
  369.      HBBox *BVtree;
  370.      HitData *hit;                  /* hit info */
  371. {
  372.   int i;
  373.   double box_hit_dist;
  374.   Ray newRay;                   /* Ray to test */
  375.   Objectt *object;
  376.   Polygon *poly;
  377.   HitData polyhit;
  378.  
  379.   if (Option.debug) {
  380.     printf("\t\tRayPoly-BVH: visible=%g\n", ray->visible);
  381.     printf("\tBox: %g,%g,%g -> %g,%g,%g\n",
  382.        BVtree->box->min.x, BVtree->box->min.y,  BVtree->box->min.z, 
  383.        BVtree->box->max.x, BVtree->box->max.y,  BVtree->box->max.z);
  384.   }
  385.  
  386.   if (ray->visible > 0.0) {        /* Ray can still "see" destination */
  387.  
  388.     /* Check for intersection with polygon in tree */
  389.     if (IsLeafBox(BVtree)) {
  390.       
  391.       /* Don't check source or receiver polygons. Can't hit themselves */
  392.       if ((BVtree->poly == shootPatch) || (BVtree->poly == recPatch))
  393.     return;
  394.  
  395.       newRay = *ray;
  396.       object = BVtree->object; poly = BVtree->poly;
  397.       if (Option.debug)
  398.     printf("\tCheck Obj/Poly: %s%d / %s%d\n", 
  399.            object->name, object->id, poly->name, poly->id);
  400.       
  401.       /* Check if hits box around poly, then if hits polygon */
  402.       polyhit = *hit;
  403.       RayStats.rayPoly++;
  404.       if (RayPolygon(poly, &newRay, &polyhit, max_distance, 
  405.              *BVtree->box, FF_Options.quadtri_ray)) {
  406.     if (polyhit.distance < max_distance) {
  407.       RayStats.intRay++;
  408.       RayStats.intPoly++;
  409.       ray->visible = 0.0;
  410.       Store_HitInter(hit,polyhit.obj, polyhit.distance,
  411.              polyhit.intersect.x, polyhit.intersect.y,
  412.              polyhit.intersect.z);
  413.     }
  414.       }
  415.       
  416.     /* Test if hit bounding volume, if so continue down tree */
  417.     } else {
  418.       RayStats.rayBox++;
  419.  
  420.       /* Don't keep track of where it hits, just if it hits */
  421.       newRay = *ray;
  422.       if (RayBoundingBox(*BVtree->box, newRay, &box_hit_dist)) {
  423.     if (box_hit_dist < hit->distance) {
  424.       RayStats.intBox++;
  425.       RayStats.intRay++;
  426.       /* RayStats.intRayID++; */
  427.       i=0;
  428.       while(i<BVtree->num_children && ray->visible > 0.0) {
  429.         RayPolyBVH(ray, max_distance, BVtree->child[i], hit);
  430.         i++;
  431.       }
  432.     }
  433.       }
  434.     }
  435.  
  436.   } 
  437. }
  438.  
  439. /**********************************************************************/
  440. /* Ray-Object-BVH traversal                                           */
  441. /* If find that object is hit and intersection distance is less that  */
  442. /* maximum distance "max_distance" then stop                          */
  443. /**********************************************************************/
  444. void RayBVH(ray, max_distance, BVtree, hit)
  445.      Ray *ray;
  446.      double max_distance;
  447.      HBBox *BVtree;
  448.      HitData *hit;                  /* hit info */
  449. {
  450.   int i;
  451.   double box_hit_dist;
  452.   Ray newRay;                   /* Ray to test */
  453.   Objectt *object;
  454.  
  455.   if (Option.debug) {
  456.     printf("\t\tRay-BVH: visible=%g\n", ray->visible);
  457.     printf("\tBox: %g,%g,%g -> %g,%g,%g\n",
  458.        BVtree->box->min.x, BVtree->box->min.y,  BVtree->box->min.z, 
  459.        BVtree->box->max.x, BVtree->box->max.y,  BVtree->box->max.z);
  460.   }
  461.  
  462.   if (ray->visible > 0.0) {        /* Ray can still "see" destination */
  463.     /* Reset_Hit(hit,max_distance); */ /* Set hit info */
  464.     
  465.     /* Check for intersection with object in tree */
  466.     if (BVtree->object != 0 && BVtree->poly == 0) {  
  467.       newRay = *ray;
  468.       object = BVtree->object;
  469.       if (Option.debug)
  470.     printf("\tChecking object: %s%d\n", object->name, object->id);
  471.       if ((Option.rayTransform) && (object->primid != MESH))
  472.     RayTransform(ray, &newRay, *object->WToM);
  473.  
  474.       /* Test mesh using BV, just to direct compare for other primitives */
  475.       if (object->primid != MESH) 
  476.     RayObject(&newRay, hit, object);
  477.       else { 
  478.     /* Use polygon BVH or traverse mesh of polygons for intersect */
  479.     if (Option.poly_grid)
  480.       RayPolyBVH(ray, max_distance, BVtree, hit);
  481.     else {
  482.       RayStats.rayBox++;
  483.       if (RayBoundingBox(*BVtree->box, newRay, &box_hit_dist)) {
  484.         if (box_hit_dist < max_distance) {
  485.           RayStats.intBox++;
  486.           RayStats.intRay++;
  487.           RayObject(&newRay, hit, object);
  488.         }
  489.       }
  490.     }
  491.       }
  492.       
  493.       /* Stop if hit an object closer than maximum distance 
  494.      ray can travel for form factors. */
  495.       if (Option.visibility == FORM_FACTOR) {
  496.     if (hit->distance < max_distance) {
  497.       RayStats.intRay++;
  498.       ray->visible = 0.0;
  499.     }
  500.       }
  501.       
  502.     /* Test if hit bounding volume, if so continue down tree */
  503.     /* Note: rays not transformed, since bounding boxes are in
  504.        world space coords already */
  505.     } else if (BVtree->poly == 0 && BVtree->object == 0) {
  506.       /* Don't keep track of where it hits, just if it hits ! */
  507.       newRay = *ray;
  508.       RayStats.rayBox++;
  509.       if (RayBoundingBox(*BVtree->box, newRay, &box_hit_dist)) {
  510.     if (box_hit_dist < hit->distance) {
  511.       RayStats.intBox++;
  512.       RayStats.intRay++;
  513.       /* RayStats.intRayID++; */
  514.       i=0;
  515.       while(i<BVtree->num_children && ray->visible > 0.0) {
  516.         RayBVH(ray, max_distance, BVtree->child[i], hit);
  517.         i++;
  518.       }
  519.     }
  520.       }
  521.     }
  522.  
  523.   } 
  524. }
  525.  
  526.